1. Field of the Invention
This invention relates generally to switches, and more particularly, but not exclusively, to a reduced memory linking list based transmit queue.
2. Description of the Related Art
Networks, such as local area networks (i.e., LANs) and wide area networks (i.e., WANs, e.g., the Internet), enable a plurality of nodes to communicate with each other. Nodes can include computers, servers, storage devices, mobile devices, PDAs, wireless telephones, etc. Networks can include the nodes themselves, a connecting medium (wired, wireless and/or a combination of wired and wireless), and network switching systems such as routers, hubs and/or switches.
The network switching systems route traffic between various nodes of the network. However, in certain circumstances the network switching systems may not be able to instantaneously route traffic to a certain node. For example, if several nodes are transmitting data to a single node, a network switching system may become overloaded with respect to that one node. In another example, the receiving node may be unable to receive data as fast as the transmitting node is transmitting the data. Accordingly, network switching systems require transmit queues (e.g., shared memory) to temporarily store received data.
Conventionally, there are two types of transmit queues that network switching systems use. The simplest and most common is the First-In First-Out (FIFO) continuous memory array. In the continuous memory array, data is written into it in order one cell after another and read out of it in order that the data was written into it. Advantages of the continuous memory arrays are that they are quite simple and direct. Further, all used entries are located continuously, making it simple to retrieve the data entries in order.
A second type of transmit queue is the linking list approach. In a linking list, a memory manager is required to allocate memory in the queue for each data entry. Further, each data entry must also indicate the location of the next data entry since the entries may not be stored continuously as in a continuous memory array. Disadvantages of this type of system is that it is more complex, it requires an extra field in the queue to record location of the next data entry, and a memory management mechanism is needed to determine empty entries in the queue. However, an advantage of this type of system is that it does not require data to be put in any specific order in the queue. Each entry can be put wherever there is free space.
However, a disadvantage of both types of transmits queues is that both require a large amount of memory. For example, a transmit queue using the continuous memory array approach will require at least 1,024 Kbits for 8 transmit queues (1 queue per port). Using a linking list approach requires at least 336 Kbits for 8 transmit queues, which is still relatively large compared to the size of the chip that the network switching system resides on. Further, due to the complexity of the linking list approach, each of the 8 transmit queues will require its own memory manager. Accordingly, a new system and method is needed that enables smaller transmit queues.